package leetcode.method.back_tracking;

/**
 * 乘法太多浪费计算时间
 */
public class Program63UniquePath3 {
    static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public Program63UniquePath3() {
    }

    public int uniquePathsIII(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;

        int startI = 0;
        int startJ = 0;
        int n = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == 0) {
                    n++;
                } else if (grid[i][j] == 1) {
                    n++;
                    startI = i;
                    startJ = j;
                }
            }
        }
        return dfs(grid, startI, startJ, n);
    }

    private int dfs(int[][] grid, int r, int c, int n) {
        if (grid[r][c] == 2) {
            return n == 0 ? 1 : 0;
        }
        int row = grid.length, col = grid[0].length;
        int value = grid[r][c];
        grid[r][c] = -1;
        int res = 0;

        for (int[] dir : dirs) {
            int i = r + dir[0], j = c + dir[1];

            if (i >= 0 && i < row && j >= 0 && j < col && (grid[i][j] == 0 || grid[i][j] == 2)) {
                res += dfs(grid, i, j, n-1);
            }
        }
        grid[r][c] = value;
        return res;
    }

    public static void main(String[] args) {
        Program63UniquePath3 myStack = new Program63UniquePath3();
        int[][] grid = {
                {1,0,0,0}
                ,{0,0,0,0}
                ,{0,0,2,-1}
        };
        System.out.println(myStack.uniquePathsIII(grid));
        int[][] grid1 = {
                {1,0,0,0}
                ,{0,0,0,0}
                ,{0,0,0,2}
        };
        System.out.println(myStack.uniquePathsIII(grid1));
        int[][] grid2 = {
                {0,1}
                ,{2,0}
        };
        System.out.println(myStack.uniquePathsIII(grid2));
    }
}
